
package main.old.new_2023.last.month_9;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 449. 序列化和反序列化二叉搜索树
 * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
 * 设计一个算法来序列化和反序列化 二叉搜索树 。对序列化/反序列化算法的工作方式没有限制。
 * 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * 编码的字符串应尽可能紧凑。
 *
 * todo 2511. 最多可以摧毁的敌人城堡数目
 * 给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：
 * -1 表示第 i 个位置 没有 城堡。
 * 0 表示第 i 个位置有一个 敌人 的城堡。
 * 1 表示第 i 个位置有一个你控制的城堡。
 *
 * 现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：
 * 0 <= i, j <= n - 1
 * 军队经过的位置 只有 敌人的城堡。正式的，对于所有 min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。
 * 当军队移动时，所有途中经过的敌人城堡都会被 摧毁 。
 * 请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队，或者没有你控制的城堡，请返回 0 。
 *
 * todo 1921. 消灭怪物的最大数量
 * 你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
 * 怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
 * 怪物从 第 0 分钟 时开始移动。你有一把武器，并可以 选择 在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
 * 一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市，这会被视为 输掉 游戏，在你可以使用武器之前，游戏就会结束。
 * 返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回  n 。
 *
 * todo 746. 使用最小花费爬楼梯
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0904 {

    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 3){
            return 0;
        }
        int[] min = new int[cost.length];
        min[0] = 0;
        min[1] = Math.min(cost[1],0);
        for (int i = 2; i<cost.length;i++){
            min[i] = Math.min(min[i-2]+cost[i],min[i-1]);
        }
        return min[min.length-1];
    }

    //消灭怪物的最大数量
    public int eliminateMaximum(int[] dist, int[] speed) {
        double[] times = new double[dist.length];
        for (int i = 0;i<dist.length;i++){
            times[i] = (double) dist[i]/speed[i];
        }
        times = Arrays.stream(times).sorted().toArray();
        int sum = 0;
        for (int i = 0;i<times.length;i++){
            if (times[i] <= i){
                return sum;
            }else {
                sum++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] dist = {3,2,4};
        int[] speed = {5,3,2};
        Solution0904 test = new Solution0904();
        test.eliminateMaximum(dist,speed);
    }

    //最多可以摧毁的敌人城堡数目
    public int captureForts(int[] forts) {
        int sum = 0;
        for (int i =0;i<forts.length;i++){
            if (forts[i] != 1){
                for (int j = i+1;j<forts.length;j++){
                    if (forts[j] != 0){
                        if (forts[i] + forts[j] >= 0){
                            sum = Math.max(sum,j -i-1);
                        }
                        i = j-1;
                        break;
                    }
                }
            }
        }
        return sum;
    }

    //序列化和反序列化二叉搜索树
    public String serialize(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        postOrder(root, list);
        String str = list.toString();
        return str.substring(1, str.length() - 1);
    }
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] arr = data.split(", ");
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            stack.push(Integer.parseInt(arr[i]));
        }
        return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
    }
    //后序遍历
    private void postOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
    private TreeNode construct(int lower, int upper, Deque<Integer> stack) {
        if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
            return null;
        }
        int val = stack.pop();
        TreeNode root = new TreeNode(val);
        root.right = construct(val, upper, stack);
        root.left = construct(lower, val, stack);
        return root;
    }

}
